package 中等.双指针;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回
 * 字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
 * <p>
 * 如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存
 * 在，则返回空字符串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting
 */
public class 通过删除字母匹配到字典里最长单词_524 {

    public static void main(String[] args) {

        System.out.println(isWord("babcdd", "abc"));
        List<String> list = new ArrayList<>();
        list.add("bc");
        list.add("abc");
        list.add("acd");
        System.out.println(findLongestWord("babcdd", list));

    }

    //不考虑提前排序，直接遍历判断是否存在字典单词，如果存在，将最长且字典序最小的字符串保存
    public static String findLongestWord(String s, List<String> dictionary) {
        String longestWord = "";
        for (String word : dictionary) {
            if (isWord(s, word)) {
                if (word.length() > longestWord.length()) {
                    longestWord = word;
                } else if (word.length() == longestWord.length() && word.compareTo(longestWord) < 0) {
                    longestWord = word;
                }
            }
        }
        return longestWord;
    }

    //使用双指针判断是否可以通过删除元素，不改变元素顺序，得到字典单词
    public static Boolean isWord(String s, String word) {
        int i = 0, j = 0;
        while (i < s.length() && j < word.length()) {
            if (s.charAt(i) == word.charAt(j)) {
                i++;
                j++;
            } else {
                i++;
            }
        }
        return j == word.length();
    }

}
